#ifndef _GRAPH_h_
#define _GRAPH_H_

#include <iostream>
#include <queue>

//从第12行至第479行为利用邻接矩阵构造的模板类Graph1，可用于实现有向图的存储。
//类里面定义的私有成员变量：
//m_pointList:图中的顶点集合
//m_collarMatrix:图对应的邻接矩阵
//m_pointCount:图中的顶点的个数
template <typename _EdgeDataType, typename _PointType>
class Graph1
{
public:
    //Graph1类的构造函数。
	Graph1(int pointCount)
	{
		init(pointCount);

        //将输入的数据信息存储到顶点集合和邻接矩阵中。
		for (int i = 0; i < m_pointCount; i++)
		{
			m_pointList[i] = _PointType();
		}

		for (int i = 0; i < m_pointCount; i++)
		{
			for (int j = 0; j < m_pointCount ; j++)
			{
				m_collarMatrix[i][j] = _EdgeDataType();
			}
		}
	}

    //Graph1类的拷贝构造函数。
	Graph1(const Graph1 & G)
	{
		init(G.m_pointCount);

		for (int i = 0; i < m_pointCount; i++)
		{
			m_pointList[i] = G.m_pointList[i];
		}

		for (int i = 0; i < m_pointCount; i++)
		{
			for (int j = 0; j < m_pointCount; j++)
			{
				m_collarMatrix[i][j] = G.m_collarMatrix[i][j];
			}
		}
	}

    //Graph1类的析构函数。
	~Graph1()
	{
		clear();
	}

    //Graph1类的拷贝赋值函数，并实现操作符=的重载。
	Graph1 & operator = (const Graph1 & G)
	{
		if (m_pointCount != 0)
		{
			clear();
		}

		init(G.m_pointCount);

		for (int i = 0; i < m_pointCount; i++)
		{
			m_pointList[i] = G.m_pointList[i];
		}

		for (int i = 0; i < m_pointCount; i++)
		{
			for (int j = 0; j < m_pointCount; j++)
			{
				m_collarMatrix[i][j] = G.m_collarMatrix[i][j];
			}
		}

		return *this;
	}

    //返回顶点个数。
	int getPointCount() const
	{
		return m_pointCount;
	}

    //返回边的个数，其中需要遍历邻接矩阵的数据。
	int getEdgeCount() const
	{
		int edgeCount = 0;
		for (int i = 0; i < m_pointCount; i++)
		{
			for (int j = 0; j < m_pointCount; j++)
			{
				if (m_collarMatrix[i][j] != _EdgeDataType())
				{
					edgeCount++;
				}
			}
		}

		return edgeCount;
	}

    //更改某个下标对应的位置的顶点的名称。
	bool setPoint(int pointIndex, _PointType pointName)
	{
		if (pointIndex < 0 || pointIndex >= m_pointCount)
		{
			return false;
		}
		
		//若图中已经有相同名称的点，则直接返回false。
		for (int i = 0; i < m_pointCount; i++)
		{
			if (m_pointList[i] == pointName)
			{
				return false;
			}
		}

		m_pointList[pointIndex] = pointName;

		return true;
	}

    //往图中添加一个点，并相应更改顶点集合和邻接矩阵的数据。
	bool addPoint(_PointType pointName)
	{
		int pointCount = m_pointCount + 1;

		//若图中已经有相同名称的点，则直接返回false。
		for (int i = 0; i < m_pointCount; i++)
		{
			if (m_pointList[i] == pointName)
			{
				return false;
			}
		}

		//新构建一个顶点集合pointList,将原来的顶点数值复制回来，并在数组最后一个位置添加新顶点。
		_PointType* pointList = new _PointType[m_pointCount + 1];
		for (int i = 0; i < m_pointCount; i++)
		{
			pointList[i] = m_pointList[i];
		}
		pointList[m_pointCount] = pointName;

		//新构建一个邻接矩阵collarMatrix,将原来的矩阵数值复制过来，并在矩阵最后一行和最后一列添加新数据。
		_EdgeDataType** collarMatrix = new _EdgeDataType*[m_pointCount + 1];
		for (int i = 0; i < m_pointCount + 1; i++)
		{
			collarMatrix[i] = new _EdgeDataType[m_pointCount + 1];
		}

		for (int i = 0; i < m_pointCount + 1; i++)
		{
			for (int j = 0; j < m_pointCount + 1; j++)
			{
				if (i < m_pointCount && j < m_pointCount)
				{
					collarMatrix[i][j] = m_collarMatrix[i][j];
				}
				else
				{
					collarMatrix[i][j] = _EdgeDataType();
				}
			}
		}

		clear();

        //将更改后的顶点集合、顶点个数、邻接矩阵重新赋值。
		m_pointCount = pointCount;
		m_pointList = pointList;
		m_collarMatrix = collarMatrix;

		return true;
	}

    //删除一个顶点，并相应修改顶点集合和邻接矩阵的数据。
	bool removePoint(_PointType pointName)
	{
		int pointCount = m_pointCount - 1;

		//若没有规定名称的顶点，即下标removeIndex越界，则直接返回false，
		//否则removeIndex就是需删除的顶点的下标。
		int removeIndex = 0;
		for (; removeIndex < m_pointCount; removeIndex++)
		{
			if (m_pointList[removeIndex] == pointName)
			{
				break;
			}
		}
		if (removeIndex == m_pointCount)
		{
			return false;
		}

		//新构建一个顶点集合pointList,将除了下标removeIndex处的位置的其他顶点数值复制回来。
		_PointType* pointList = new _PointType[m_pointCount - 1];
		for (int i = 0; i < m_pointCount - 1; i++)
		{
			if (i < removeIndex)
			{
				pointList[i] = m_pointList[i];
			}
			else
			{
				pointList[i] = m_pointList[i + 1];
			}
		}

		//新构建一个邻接矩阵collarMatrix,将除了下标removeIndex所在的行和列位置的矩阵数值复制过来。
		_EdgeDataType** collarMatrix = new _EdgeDataType * [m_pointCount - 1];
		for (int i = 0; i < m_pointCount - 1; i++)
		{
			collarMatrix[i] = new _EdgeDataType[m_pointCount - 1];
		}

		for (int i = 0; i < m_pointCount - 1; i++)
		{
			for (int j = 0; j < m_pointCount - 1; j++)
			{
				if (i < removeIndex && j < removeIndex)
				{
					collarMatrix[i][j] = m_collarMatrix[i][j];
				}
				else if (i < removeIndex && j >= removeIndex)
				{
					collarMatrix[i][j] = m_collarMatrix[i][j + 1];
				}
				else if (i >= removeIndex && j < removeIndex)
				{
					collarMatrix[i][j] = m_collarMatrix[i + 1][j];
				}
				else
				{
					collarMatrix[i][j] = m_collarMatrix[i + 1][j + 1];
				}
			}
		}

		clear();

        //将更改后的顶点集合、顶点个数、邻接矩阵重新赋值。
		m_pointCount = pointCount;
		m_pointList = pointList;
		m_collarMatrix = collarMatrix;

		return true;
	}

    //添加一条有向边。
	bool addEdge(_PointType firstPoint, _PointType secondePoint, _EdgeDataType edgeValue)
	{
		//若权重数值为空，则直接返回false。
		if (edgeValue == _EdgeDataType())
		{
			return false;
		}

		//若没有与firstPoint名称相同的顶点，即下标firstPointIndex越界，则直接返回false,
		//否则firstPointIndex就是需添加的边的第一个顶点的下标。
		int firstPointIndex = 0;
		for (; firstPointIndex < m_pointCount; firstPointIndex++)
		{
			if (m_pointList[firstPointIndex] == firstPoint)
			{
				break;
			}
		}
		if (firstPointIndex == m_pointCount)
		{
			return false;
		}

		//类似寻找与secondPoint名称相同的顶点下标。
		int secondPointIndex = 0;
		for (; secondPointIndex < m_pointCount; secondPointIndex++)
		{
			if (m_pointList[secondPointIndex] == secondePoint)
			{
				break;
			}
		}
		if (secondPointIndex == m_pointCount)
		{
			return false;
		}

		//在矩阵对应位置赋值。
		m_collarMatrix[firstPointIndex][secondPointIndex] = edgeValue;

		return true;
	}

    //设置图中某条已有的有向边的权重数值。
	bool setEdge(_PointType firstPoint, _PointType secondePoint, _EdgeDataType edgeValue)
	{
		//若权重数值为空，则直接返回false。
		if (edgeValue == _EdgeDataType())
		{
			return false;
		}

		//若没有与firstPoint名称相同的顶点，即下标firstPointIndex越界，则直接返回false,
		//否则firstPointIndex就是需更改的边的第一个顶点的下标。
		int firstPointIndex = 0;
		for (; firstPointIndex < m_pointCount; firstPointIndex++)
		{
			if (m_pointList[firstPointIndex] == firstPoint)
			{
				break;
			}
		}
		if (firstPointIndex == m_pointCount)
		{
			return false;
		}

		//类似寻找与secondPoint名称相同的顶点下标。
		int secondPointIndex = 0;
		for (; secondPointIndex < m_pointCount; secondPointIndex++)
		{
			if (m_pointList[secondPointIndex] == secondePoint)
			{
				break;
			}
		}
		if (secondPointIndex == m_pointCount)
		{
			return false;
		}
		//在矩阵对应位置赋值。
		m_collarMatrix[firstPointIndex][secondPointIndex] = edgeValue;

		return true;
	}

    //删除一条有向边。
	bool removeEdge(_PointType firstPoint, _PointType secondePoint)
	{
		//若没有与firstPoint名称相同的顶点，即下标firstPointIndex越界，则直接返回false,
		//否则firstPointIndex就是需删除的顶点的下标。		
		int firstPointIndex = 0;
		for (; firstPointIndex < m_pointCount; firstPointIndex++)
		{
			if (m_pointList[firstPointIndex] == firstPoint)
			{
				break;
			}
		}
		if (firstPointIndex == m_pointCount)
		{
			return false;
		}

		//类似寻找与secondPoint名称相同的顶点下标。
		int secondPointIndex = 0;
		for (; secondPointIndex < m_pointCount; secondPointIndex++)
		{
			if (m_pointList[secondPointIndex] == secondePoint)
			{
				break;
			}
		}
		if (secondPointIndex == m_pointCount)
		{
			return false;
		}

		//在矩阵对应位置赋值为空。
		m_collarMatrix[firstPointIndex][secondPointIndex] = _EdgeDataType();

		return true;
	}

    //题目要求中的listVertexes函数，列出全部顶点。
	void listVertexes() const
	{
		//若顶点个数为0，则无需操作。
		if (m_pointCount == 0)
		{
			return;
		}

        //遍历顶点集合m_pointList中的所有数据，并输出。
		std::cout << "[";
		for (int j = 0; j < m_pointCount - 1; j++)
		{
			std::cout << m_pointList[j] << ", ";
		}
		std::cout << m_pointList[m_pointCount - 1] << "]" << std::endl;
	}

    //题目要求中的listEdges函数，列出全部边。
	void listEdges() const
	{
		//若顶点个数为0，则无需操作。
		if (m_pointCount == 0)
		{
			return;
		}

		//遍历邻接矩阵中的所有元素，并输出。
		for (int i = 0; i < m_pointCount; i++)
		{
			for (int j = 0; j < m_pointCount; j++)
			{
                if(m_collarMatrix[i][j] != 0)
                {
                    std::cout << "( " << m_pointList[i] << " , " << m_pointList[j] << " , ";
				    std::cout << m_collarMatrix[i][j] << " )" << std::endl;
                }
			}
		}
	}

protected:
    //初始化函数，构造新的顶点集合和邻接矩阵。
	void init(int pointCount)
	{
		if (pointCount <= 0)
		{
			m_collarMatrix = nullptr;
			m_pointList = nullptr;
			m_pointCount = 0;
		}
		else
		{
			m_pointList = new _PointType[pointCount];

			m_collarMatrix = new _EdgeDataType * [pointCount];
			for (int i = 0; i < pointCount; i++)
			{
				m_collarMatrix[i] = new _EdgeDataType[pointCount];
			}

			m_pointCount = pointCount;
		}
	}

    //清空整个图的数据，释放内存。
	void clear()
	{
		if (m_pointList != nullptr)
		{
			delete[]m_pointList;
			m_pointList = nullptr;
		}

		if (m_collarMatrix != nullptr)
		{
			for (int i = 0; i < m_pointCount; i++)
			{
				delete[]m_collarMatrix[i];
				m_collarMatrix[i] = nullptr;
			}

			delete[]m_collarMatrix;
			m_collarMatrix = nullptr;
		}

		m_pointCount = 0;
	}

private:
	_PointType* m_pointList;
	_EdgeDataType** m_collarMatrix;
	int m_pointCount;
};


//从第487行至第1040行为利用邻接表构造的模板类Graph2，可用于实现有向图的存储。
//类里面定义的私有成员变量：
//m_vertexList:图中的顶点集合
//m_edgeCount:图中的边的数量
//m_vertexCount:图中的顶点的个数
template <typename _EdgeType>
struct Edge
{
	_EdgeType m_value;    //边上的权重数值。
	int m_adjacency;    //这条边对应的邻接顶点的下标。
	Edge* m_next;	//与原来的顶点对应的下一个邻接点对应的那条边的指针。

	Edge() : m_value(_EdgeType()), m_adjacency(-1), m_next(nullptr) {}
	Edge(_EdgeType value) : m_value(value), m_adjacency(-1), m_next(nullptr) {}
	Edge(_EdgeType value, Edge* next) : m_value(value), m_adjacency(-1), m_next(next) {}
	Edge(_EdgeType value, int adjacency) : m_value(value), m_adjacency(adjacency), m_next(nullptr) {}
	Edge(_EdgeType value, int adjacency, Edge* next) : m_value(value), m_adjacency(adjacency), m_next(next) {}
};

template <typename _EdgeType, typename _VertexType>
struct Vertex
{
	_VertexType m_name;    //顶点的数值。
	Edge<_EdgeType>* m_firstEdge;	//该顶点的第一个邻接点对应的那条边。

	Vertex() : m_name(_VertexType()), m_firstEdge(nullptr) {}
	Vertex(_VertexType name) : m_name(name), m_firstEdge(nullptr) {}
	Vertex(_VertexType name, Edge<_EdgeType>* firstEdge) : m_name(name), m_firstEdge(firstEdge) {}
};

template <typename _EdgeType, typename _VertexType>
class Graph2
{
	using _VertexPtr = Vertex<_EdgeType, _VertexType>*;
	using _EdgePtr = Edge<_EdgeType>*;
public:

    //Graph2类的构造函数。
	Graph2(size_t vertexCount)
	{
		init(vertexCount);
	}

    //Graph2类的拷贝构造函数。
	Graph2(const Graph2 & ALG)
	{
		init(ALG.m_vertexCount);
		copy(ALG);
	}

    //Graph2类的析构函数。
	~Graph2()
	{
		clear();
	}

    //Graph2类的拷贝赋值函数，并实现操作符=的重载。
	Graph2 & operator = (const Graph2 & ALG)
	{
		clear();
		init(ALG.m_vertexCount);
		copy(ALG);
		return *this;
	}

    //返回顶点的个数。
	size_t vertexCount() const
	{
		return m_vertexCount;
	}

    //返回边的个数。
	size_t edgeCount() const
	{
		return m_edgeCount;
	}

    //更改某个下标对应位置的顶点的名称。
	bool setVertexName(int vertexIndex, _VertexType vertexName)
	{
		//若下标数值不在区间内，则直接返回false。
		if (vertexIndex < 0 || vertexIndex >= m_vertexCount)
		{
			return false;
		}

		//遍历顶点集合m_vertexList,寻找与vertexName名称相同的顶点位置。
		int index = 0;
		while (index < m_vertexCount)
		{
			if (m_vertexList[index].m_name == vertexName)
			{
				return false;
			}

			index++;
		}

		m_vertexList[vertexIndex].m_name = vertexName;

		return true;
	}

    //添加一个顶点。
	bool addVertex(_VertexType vertexName)
	{
		//若图中已经有与vertexName名称相同的点，则直接返回false。
		for (int i = 0; i < m_vertexCount; i++)
		{
			if (m_vertexList[i].m_name == vertexName)
			{
				return false;
			}
		}

		//新构建一个顶点集合vertexList，将原来顶点集合的数据复制进去，并在数组最后一个位置新定义一个顶点。
		_VertexPtr vertexList = new Vertex<_EdgeType, _VertexType>[m_vertexCount + 1];
		for (int i = 0; i < m_vertexCount; i++)
		{
			vertexList[i] = m_vertexList[i];
		}
		vertexList[m_vertexCount].m_name = vertexName;

		//将更改后的顶点集合赋值到m_vertexList中。
		delete[]m_vertexList;
		m_vertexList = vertexList;

		m_vertexCount++;

		return true;
	}

    //删除一个已有顶点。
	bool removeVertex(_VertexType vertexName)
	{
		//若图中没有与vertexName名称相同的顶点，则直接返回false，
		//否则rmIndex就是需删除的顶点的下标。
		int rmIndex = 0;
		for (; rmIndex < m_vertexCount; rmIndex++)
		{
			if (m_vertexList[rmIndex].m_name == vertexName)
			{
				break;
			}
		}
		if (rmIndex == m_vertexCount)
		{
			return false;
		}

		_EdgePtr edge = m_vertexList[rmIndex].m_firstEdge;
		while(edge)
		{
			m_edgeCount--;
			edge = edge->m_next;
		}

		//新构建一个顶点集合vertexList,将除了下标rmIndex处的位置的其他顶点数值复制回来。
		_VertexPtr vertexList = new Vertex<_EdgeType, _VertexType>[m_vertexCount - 1];
		for (int i = 0; i < m_vertexCount - 1; i++)
		{
			if (i < rmIndex)
			{
				vertexList[i] = m_vertexList[i];
			}
			else
			{
				vertexList[i] = m_vertexList[i + 1];
			}
		}
		//将更改后的顶点集合赋值到m_vertexList中。
		delete[]m_vertexList;
		m_vertexList = vertexList;

		m_vertexCount--;	

		//遍历新的顶点集合m_vertexList中的所有顶点，寻找有一个端点为vertexName的所有边。
		for (int index = 0; index < m_vertexCount; index++)
		{
			if (m_vertexList[index].m_firstEdge == nullptr)
			{
				continue;
			}
			//对于某个顶点只有一个邻接顶点的情况。
			else if (m_vertexList[index].m_firstEdge->m_next == nullptr)
			{
				if (m_vertexList[index].m_firstEdge->m_adjacency == rmIndex)
				{
					delete m_vertexList[index].m_firstEdge;
					m_vertexList[index].m_firstEdge = nullptr;
					m_edgeCount--;
				}
				else
				{
					continue;
				}
			}
			//对于某个顶点有多个邻接顶点的情况，用while循环寻找。
			else
			{
				_EdgePtr preEdge = m_vertexList[index].m_firstEdge;    //当前位置的对应边。
				_EdgePtr currEdge = preEdge->m_next;    //下一个邻接顶点的对应边，可用于越界检测。

				//第一个邻接顶点的下标就是rmIndex，则在当前位置删除即可。
				if (preEdge->m_adjacency == rmIndex)
				{
					m_vertexList[index].m_firstEdge = currEdge;

					delete preEdge;
					preEdge = nullptr;
					m_edgeCount--;
				}
				//否则在currEdge不为空的条件下向后寻找。
				else
				{
					while (currEdge)
					{
						if (currEdge->m_adjacency == rmIndex)
						{
							preEdge->m_next = currEdge->m_next;

							delete currEdge;
							currEdge = nullptr;
							m_edgeCount--;

							break;
						}
						preEdge = currEdge;
						currEdge = currEdge->m_next;
					}
				}
			}
		}

		//若按照上面的代码进行删除操作，在被删除的顶点之后的顶点的下标会减一，从而让之前与之相关的
		//邻接边的m_adjacency产生偏差，所以在函数最后添加一段代码，将那些邻接边的m_adjacency数值
		//减一，从而指向正确的邻接顶点。
		for (int index = 0; index < m_vertexCount; index++)
		{
			if (m_vertexList[index].m_firstEdge == nullptr)
			{
				continue;
			}
			_EdgePtr Edge = m_vertexList[index].m_firstEdge;
			while(Edge)
			{
				if(Edge->m_adjacency > rmIndex)
				{
					Edge->m_adjacency--;
				}
				Edge = Edge->m_next;
			}
		}

		return true;
	}

    //更改图中某条边的权重。
	bool setEdgeValue(_VertexType firstVertexName, _VertexType secondeVertexName, _EdgeType value)
	{
		int firstVertexIndex = -1;
		int secondeVertexIndex = -1;
		//分别寻找与firstVertexName和secondVertexName名称相同的顶点的下标。
		for (int index = 0; index < m_vertexCount; index++)
		{
			if (m_vertexList[index].m_name == firstVertexName)
			{
				firstVertexIndex = index;
			}

			if (m_vertexList[index].m_name == secondeVertexName)
			{
				secondeVertexIndex = index;
			}
		}
		//若没找到顶点位置或者两个顶点相同，则直接返回false。
		if (firstVertexIndex == -1 || secondeVertexIndex == -1 || firstVertexIndex == secondeVertexIndex)
		{
			return false;
		}
		//若下标firstVertexName位置的顶点没有连着的边，即没有邻接顶点，则直接返回false。
		if (m_vertexList[firstVertexIndex].m_firstEdge == nullptr)
		{
			return false;
		}
		else
		{
			//利用while循环向后寻找另一个端点为secondVertexName下标位置的顶点对应的边。
			_EdgePtr firstEdge = m_vertexList[firstVertexIndex].m_firstEdge;
			while (firstEdge)
			{
				if (firstEdge->m_adjacency == secondeVertexIndex)
				{
					firstEdge->m_value = value;
					break;
				}
				firstEdge = firstEdge->m_next;
			}

			if (firstEdge == nullptr)
			{
				return false;
			}
		}

		return true;
	}

    //添加一条边。
	bool addEdge(_VertexType firstVertexName, _VertexType secondeVertexName, _EdgeType value)
	{
		int firstVertexIndex = -1;
		int secondeVertexIndex = -1;
		//分别寻找与firstVertexName和secondVertexName名称相同的顶点的下标。
		for (int index = 0; index < m_vertexCount; index++)
		{
			if (m_vertexList[index].m_name == firstVertexName)
			{
				firstVertexIndex = index;
			}

			if (m_vertexList[index].m_name == secondeVertexName)
			{
				secondeVertexIndex = index;
			}
		}
		//若没找到顶点位置或者两个顶点相同，则直接返回false。
		if (firstVertexIndex == -1 || secondeVertexIndex == -1 || firstVertexIndex == secondeVertexIndex)
		{
			return false;
		}
		//若firstVertexIndex位置的顶点没有边连接，则直接新建一条边，并设置secondVertexIndex位置的顶点为邻接顶点。
		if (m_vertexList[firstVertexIndex].m_firstEdge == nullptr)
		{
			m_vertexList[firstVertexIndex].m_firstEdge = new Edge<_EdgeType>(value, secondeVertexIndex);
		}
		//利用false循环向后寻找另一个端点为secondVertexName下标位置的顶点对应的边。
		//如果有，则直接返回false。
		else
		{
			_EdgePtr firstEdge = m_vertexList[firstVertexIndex].m_firstEdge;
			while (firstEdge->m_next)
			{
				if (firstEdge->m_adjacency == secondeVertexIndex)
				{
					return false;
				}
				firstEdge = firstEdge->m_next;
			}
			//在最后一个邻接顶点处判断，如果同样不是secongVertexIndex位置的点，则直接在最后的位置添加边和邻接顶点。
			if (firstEdge->m_adjacency == secondeVertexIndex)
			{
				return false;
			}
			firstEdge->m_next = new Edge<_EdgeType>(value, secondeVertexIndex);
		}

		m_edgeCount++;

		return true;
	}

    //删除一条边。
	bool removeEdge(_VertexType firstVertexName, _VertexType secondeVertexName)
	{
		int firstVertexIndex = -1;
		int secondeVertexIndex = -1;
		//分别寻找与firstVertexName和secondVertexName名称相同的顶点的下标。
		for (int index = 0; index < m_vertexCount; index++)
		{
			if (m_vertexList[index].m_name == firstVertexName)
			{
				firstVertexIndex = index;
			}

			if (m_vertexList[index].m_name == secondeVertexName)
			{
				secondeVertexIndex = index;
			}
		}
		//若没找到顶点位置或者两个顶点相同，则直接返回false。
		if (firstVertexIndex == -1 || secondeVertexIndex == -1 || firstVertexIndex == secondeVertexIndex)
		{
			return false;
		}
		//若firstVertexIndex位置的顶点没有连着的边，即没有邻接顶点，则直接返回false。
		if (m_vertexList[firstVertexIndex].m_firstEdge == nullptr)
		{
			return false;
		}
		//只有一个邻接顶点的情况。
		else if (m_vertexList[firstVertexIndex].m_firstEdge->m_next == nullptr)
		{
			if (m_vertexList[firstVertexIndex].m_firstEdge->m_adjacency == secondeVertexIndex)
			{
				delete m_vertexList[firstVertexIndex].m_firstEdge;
				m_vertexList[firstVertexIndex].m_firstEdge = nullptr;
			}
			else
			{
				return false;
			}
		}
		//有多个邻接顶点的情况，利用while循环向后寻找。
		else
		{
			_EdgePtr preEdge = m_vertexList[firstVertexIndex].m_firstEdge;
			_EdgePtr currEdge = preEdge->m_next;
			//第一个邻接顶点正好是secondVertexIndex位置的顶点的情况。
			if (preEdge->m_adjacency == secondeVertexIndex)
			{
				m_vertexList[firstVertexIndex].m_firstEdge = currEdge;

				delete preEdge;
				preEdge = nullptr;
			}
			else
			{
				while (currEdge)
				{
					if (currEdge->m_adjacency == secondeVertexIndex)
					{
						preEdge->m_next = currEdge->m_next;

						delete currEdge;
						currEdge = nullptr;

						break;
					}
					preEdge = currEdge;
					currEdge = currEdge->m_next;
				}
			}
		}

		m_edgeCount--;

		return true;
	}

    //题目要求中的listVertexes函数，列出全部顶点。
	void listVertexes() const
	{
		//若顶点个数为0，则无需操作。
		if (m_vertexCount == 0)
		{
			return;
		}

        //遍历顶点集合m_vertexList中的所有数据，并输出。
		std::cout << "[";
		for (int j = 0; j < m_vertexCount - 1; j++)
		{
			std::cout << m_vertexList[j].m_name << ", ";
		}
		std::cout << m_vertexList[m_vertexCount - 1].m_name << "]" << std::endl;
	}

    //题目要求中的listEdges函数，列出全部有向边。
	void listEdges() const
	{
		//若顶点个数为0，则无需操作。
        if (m_edgeCount == 0)
		{
			return;
		}
		//遍历所有顶点的所有邻接顶点,对于每一个点用while循环向后寻找邻接顶点。
		for(int index = 0; index < m_vertexCount; index++)
		{
			if(m_vertexList[index].m_firstEdge != nullptr)
			{
				_EdgePtr currEdge = m_vertexList[index].m_firstEdge;
				while (currEdge)
				{
                	std::cout << "( ";
					std::cout << m_vertexList[index].m_name << " , " << m_vertexList[currEdge->m_adjacency].m_name << " , " << currEdge->m_value;
					std::cout << " )" << std::endl;

					currEdge = currEdge->m_next;
				}
			}
		}
	}

protected:
    //初始化函数。
	void init(size_t vertexCount)
	{
		m_vertexCount = vertexCount;
		m_edgeCount = 0;
		if (m_vertexCount == 0)
		{
			m_vertexList = nullptr;
		}
		else
		{
			m_vertexList = new Vertex<_EdgeType, _VertexType>[m_vertexCount];
		}
	}

    //清空整个图的数据，释放内存。
	void clear()
	{
		if (m_vertexList == nullptr)
		{
			return;
		}

		int index = 0;
		while (index < m_vertexCount)
		{
			_EdgePtr currEdge = m_vertexList[index].m_firstEdge;
			while (currEdge != nullptr)
			{
				_EdgePtr edge = currEdge;
				currEdge = currEdge->m_next;

				delete edge;
				edge = nullptr;
			}

			index++;
		}

		delete[]m_vertexList;
		m_vertexList = nullptr;

		m_vertexCount = 0;
	}

    //复制图的数据，将图ALG中的数据复制到当前图中。
	void copy(const Graph2 & ALG)
	{
		
		int index = 0;
		while (index < m_vertexCount)
		{
			_EdgePtr& myCurrEdge = m_vertexList[index].m_firstEdge;
			_EdgePtr ALGCurrEdge = ALG.m_vertexList[index].m_firstEdge;
			while (ALGCurrEdge != nullptr)
			{
				myCurrEdge = new Edge<_EdgeType>(ALGCurrEdge->m_value);
				myCurrEdge = myCurrEdge->m_next;

				ALGCurrEdge = ALGCurrEdge->m_next;
			}

			m_vertexList[index].m_name = ALG.m_vertexList[index].m_name;
			
			index++;
		}
		m_edgeCount = ALG.m_edgeCount;
	}

private:
	_VertexPtr m_vertexList;
	size_t m_vertexCount;
	size_t m_edgeCount;
};


#endif
